import collections
class Solution(object):
    def minDistance(self, houses, k):
        houses.sort()
        n = len(houses)
        DP = [[float('inf') for _ in range(k)] for _ in range(n)]
        for i in range(n):
            for j in range(min(k, i + 1)):
                val = 0
                if j == 0:
                    for t in range(i):
                        val += houses[i] - houses[t]
                    DP[i][j] = val
                else:
                    now_val = 0
                    st = collections.deque()
                    for t in range(i - 1, j - 2, -1):
                        if t == i - 1:
                            DP[i][j] = min(DP[t][j - 1], DP[i][j])
                        else:
                            st.append(t + 1)
                            now_val += len(st) * (houses[t + 1] - houses[t])
                            while st and houses[st[0]] - houses[t] >= houses[i] - houses[st[0]]:
                                index = st.popleft()
                                now_val += houses[i] - houses[index] - (houses[index] - houses[t])
                            DP[i][j] = min(DP[t][j - 1] + now_val, DP[i][j])
        min_val = float('inf')
        now_val = 0
        now_length = 0
        for i in range(n - 1, k - 2, -1):
            if i == n - 1:
                min_val = min(min_val, DP[i][k - 1])
            else:
                now_val += now_length * (houses[i + 1] - houses[i])
                min_val = min(min_val, DP[i][k - 1] + now_val)
            now_length += 1
        return min_val


data = Solution()
houses = [1, 4, 8, 10, 20]
k = 3
print(data.minDistance(houses, k))
